DP W

0と1からなる長さ20万の列があって「この範囲に1があれば何点」というルールが20万個ある、最良の列を作ったら何点になるか求めよ

素朴に実装したらどうなるか

2^200000の各数列に対してスコア計算してmax→やばい

各数列について計算する代わりに、途中までの結果を使って効率よく計算できないか？

dp[i] = （i まで決めたときに）最後に1にしたのが i であるときのmax。遷移は dp[i] = min(dp[j] | j=0~i-1) 。その後、区間 [l,i] について dp[l~i] に a を足しこむということをやる。segtreeで高速化する（区間addと区間minができれば良い）O((N+M) log N)

なんかこれは自分は典型化できてなかった（ので説明がふわっとしてしまっている）